package sort;

public class InsertSort {
    private InsertSort() {
    }

    // 编写插入排序
    public static <E extends Comparable<E>> void sort(E [] arr) {
        // 注意：这里必须比到最后一个元素，和选择排序不同，插入排序只会处理前i个元素，而第i个后面的元素都是原来的位置，所以最后一个元素也要记得排序
        // 但是选择排序是每轮都将最小的元素取出来排到前面，那么排好前n-1个元素之后iu，第n个元素自然就排好了
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j >= 1; j--) {
                // 如果后面的数比前面的小就交换位置
                if(arr[j].compareTo(arr[j-1]) < 0){
                    swap(arr,j,j-1);
                }
                // 否则就是大于等于前面的数，由于前面的数已经排序好了，所以无需再比了，直接退出
                else {
                    break;
                }
            }
        }
    }

    // 交换两个元素的位置
    private static <E> void swap(E [] arr, int i, int j){
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
